//反转一个单链表。 
//
// 示例: 
//
// 输入: 1->2->3->4->5->NULL
//输出: 5->4->3->2->1->NULL 
//
// 进阶: 
//你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 
// Related Topics 链表 
// 👍 1090 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：反转链表
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P206_ReverseLinkedList {
    public static void main(String[] args) {
        Solution solution = new P206_ReverseLinkedList().new Solution();
        ListNode node = MyUtil.createNode(1, 2, 3, 4, 5, 6, 7, 8);
        ListNode reverse = solution.reverseList(node);
        MyUtil.printListNode(reverse);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
//    /**
//     * 迭代
//     * 时间复杂度 O(n)
//     */
//    class Solution {
//        public ListNode reverseList(ListNode head) {
//            ListNode curr = head, temp = null, pre = null;
//            while (curr != null) {
//                temp = curr.next;
//                curr.next = pre;
//                pre = curr;
//                curr = temp;
//            }
//            return pre;
//        }
//    }

    /**
     * 递归
     * 时间复杂度 O(n)
     */
    class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode p = reverseList(head.next);
            head.next.next = head;
            // 防止形成环
            head.next = null;
            return p;
        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

}
